Many distance transform algorithms are known which take a 2D, 3D or higher dimensional image comprising one or more objects and produce a distance image, corresponding to the input image and having a distance value at each image element. The distance transform algorithm aims to assign points in the distance image the minimum distance from that particular point to the nearest point on the border of any object in the input image. In some cases every point in the distance image is assigned a distance value and this includes points within objects as well as those in the background. For example, the sign of the assigned distance value may indicate whether the point is inside or outside an object.
Distance transforms are required in many image processing application domains including but not limited to medical image analysis, analysis of images of natural scenes, robotics, ray-tracing, automated classification of biological images, hands-free user interfaces, and others.
Various types of distance transforms are known such as Euclidean and Geodesic distance transforms. For example, the shortest geodesic distance between two points in an image may be one that travels around a region of high gradient rather than a Euclidean shortest path which travels “as the crow flies”.
There is a desire to provide distance transform engines that operate in real time and with high levels of accuracy.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known distance transform engines.